package leetcode;

import java.util.Arrays;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * Given an array S of n integers, find three integers in S such that the sum is
 * closest to a given number, target. Return the sum of the three integers. You
 * may assume that each input would have exactly one solution.
 * 
 * For example, given array S = {-1 2 1 -4}, and target = 1.
 * 
 * The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
 * 
 * @author yunzhang
 * 
 */
public class ThreeSumClosest {

	private ThreeSumClosest instance;

	public int threeSumClosest(int[] num, int target) {
		if (num == null || num.length < 3)
			return -1;

		Arrays.sort(num);
		int closest = num[0] + num[1] + num[2];
		for (int a = 0; a < num.length - 2; ++a) {
			int twoTar = target - num[a];
			int b = a + 1;
			int c = num.length - 1;
			int preClosest = Integer.MAX_VALUE;
			while (b < c) {
				int dist = twoTar - num[b] - num[c];
				if (dist == 0)
					return target;
				else if (dist > 0) {
					if (dist <= preClosest) {
						++b;
						preClosest = dist;
						if (dist < Math.abs(target - closest))
							closest = target - dist;
					} else
						break;
				} else {
					dist = -dist;
					if (dist <= preClosest) {
						--c;
						preClosest = dist;
						if (dist < Math.abs(target - closest))
							closest = target + dist;
					} else
						break;
				}
			}
		}

		return closest;
	}

	@Before()
	public void init() {
		instance = new ThreeSumClosest();
	}

	@Test
	public void test1() {
		int[] num = new int[] { -1, 2, 1, -4 };
		int target = 1;
		int ret = instance.threeSumClosest(num, target);
		Assert.assertEquals(2, ret);
	}

	@Test
	public void test2() {
		int[] num = new int[] { 0, 2, 1, -3 };
		int target = 1;
		int ret = instance.threeSumClosest(num, target);
		Assert.assertEquals(0, ret);
	}

	@Test
	public void test3() {
		int[] num = new int[] { 87, 6, -100, -19, 10, -8, -58, 56, 14, -1, -42,
				-45, -17, 10, 20, -4, 13, -17, 0, 11, -44, 65, 74, -48, 30,
				-91, 13, -53, 76, -69, -19, -69, 16, 78, -56, 27, 41, 67, -79,
				-2, 30, -13, -60, 39, 95, 64, -12, 45, -52, 45, -44, 73, 97,
				100, -19, -16, -26, 58, -61, 53, 70, 1, -83, 11, -35, -7, 61,
				30, 17, 98, 29, 52, 75, -73, -73, -23, -75, 91, 3, -57, 91, 50,
				42, 74, -7, 62, 17, -91, 55, 94, -21, -36, 73, 19, -61, -82,
				73, 1, -10, -40, 11, 54, -81, 20, 40, -29, 96, 89, 57, 10, -16,
				-34, -56, 69, 76, 49, 76, 82, 80, 58, -47, 12, 17, 77, -75,
				-24, 11, -45, 60, 65, 55, -89, 49, -19, 4 };
		int target = -275;
		int ret = instance.threeSumClosest(num, target);
		Assert.assertEquals(-274, ret);
	}
}
